/**
 * Copyright (C), 2019-2022, 宇信融汇
 * FileName: TestBinary
 * Author:   86182
 * Date:     2022/4/14 16:30
 * Description:
 * History:
 * <author>          <time>          <version>          <desc>
 * 86182           修改时间           版本号              描述
 */
package com.binary;

/**
 * @Classname TestBinary
 * @Description 二分查找
 * 1. 前提：有已排序数组 A（假设已经做好）
 * <p>
 * 2. 定义左边界 L、右边界 R，确定搜索范围，循环执行二分查找（3、4两步）
 * <p>
 * 3. 获取中间索引 M = Floor((L+R) /2)
 * <p>
 * 4. 中间索引的值  A[M] 与待搜索的值 T 进行比较
 * ① A[M] == T 表示找到，返回中间索引
 * <p>
 * ② A[M] > T，中间值右侧的其它元素都大于 T，无需比较，中间索引左边去找，M - 1 设置为右边界，重新查找
 * <p>
 * ③ A[M] < T，中间值左侧的其它元素都小于 T，无需比较，中间索引右边去找， M + 1 设置为左边界，重新查找
 * <p>
 * 5. 当 L > R 时，表示没有找到，应结束循环
 * @Date 2022/4/14 16:30
 * @Created by 86182
 */
public class TestBinary {

    public static void main(String[] args) {
        int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};
        int target = 1;
        int idx = TestBinary.binarySearch(array, target);

        int a = 2;


        System.out.println(100>>>3);

        System.out.println(idx);
    }

    public static int binarySearch(int[] a, int t) {
        int l = 0, r = a.length - 1, m = 0;
        while (r >= l) {
            m = (r + l) / 2;
            if (a[m] == t) {
                return m;
            } else if (a[m] > t) {
                r = m - 1;
            } else {
                l = m + 1;
            }

        }
        return -1;
    }
}
